package com.learn.algorithm.dynamic.programming;

public class LeetCode329 {
    public static int longestIncreasingPath(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        int[][] dp = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                ans = Math.max(ans, f2(matrix, i, j, dp));
            }
        }
        return ans;
    }

    public static int f2(int[][] matrix, int i, int j, int[][] dp) {
        if (dp[i][j] != 0) {
            return dp[i][j];
        }
        int ans = 0;
        if (i > 0 && matrix[i - 1][j] > matrix[i][j]) {
            ans = Math.max(ans, f2(matrix, i - 1, j, dp));
        }
        if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j]) {
            ans = Math.max(ans, f2(matrix, i + 1, j, dp));
        }
        if (j > 0 && matrix[i][j - 1] > matrix[i][j]) {
            ans = Math.max(ans, f2(matrix, i, j - 1, dp));
        }
        if (j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j]) {
            ans = Math.max(ans, f2(matrix, i, j + 1, dp));
        }
        dp[i][j] = ans + 1;
        return ans + 1;
    }

    public static int f1(int[][] matrix, int i, int j) {
        int ans = 0;
        if (i > 0 && matrix[i - 1][j] > matrix[i][j]) {
            ans = Math.max(ans, f1(matrix, i - 1, j));
        }
        if (i + 1 < matrix.length && matrix[i + 1][j] > matrix[i][j]) {
            ans = Math.max(ans, f1(matrix, i + 1, j));
        }
        if (j > 0 && matrix[i][j - 1] > matrix[i][j]) {
            ans = Math.max(ans, f1(matrix, i, j - 1));
        }
        if (j + 1 < matrix[0].length && matrix[i][j + 1] > matrix[i][j]) {
            ans = Math.max(ans, f1(matrix, i, j + 1));
        }
        return ans + 1;
    }

    public static void main(String[] args) {
        System.out.println(longestIncreasingPath(new int[][]{{9, 9, 4}, {6, 6, 8}, {2, 1, 1}}));
    }
}
